package com.gaogzhen.datastructure.graph.undirected;

import com.gaogzhen.datastructure.stack.Stack;
import edu.princeton.cs.algs4.Graph;
import edu.princeton.cs.algs4.Queue;

import java.util.*;

/**
 * 无向图连通分量
 * @author: Administrator
 * @createTime: 2023/03/08 20:18
 */
public class CC {
    /**
     * 顶点是否标记数组
     */
    private boolean[] marked;

    /**
     * 顶点所在连通分量标志:0~count()-1
     */
    private int[] id;

    /**
     * 每个连通分量顶点数量
     */
    private int[] size;

    /**
     * 连通分量数量
     */
    private int count;

    /**
     * 要处理的无向图
     */
    private Graph graph;

    /**
     * 计算给定无向图的连通分量
     * @param graph 指定的无向图
     */
    public CC(Graph graph) {
        this.graph = graph;
        int len = graph.V();
        // 初始化
        marked = new boolean[len];
        id = new int[len];
        size = new int[len];
        // 搜索连通分量
        dfs();
    }

    /**
     * 深度优先搜索连通分量
     */
    private void dfs() {
        // 深度优先非递归实现，借助栈
        Stack<Iterator<Integer>> c = new Stack<>();
        // 搜索连通分量
        for (int v = 0; v < graph.V(); v++) {
            // 遍历图中所有顶点，以没有被标记过的顶点为起点，搜索连通分量
            // 执行完一次bsf，标记一个包含顶点v的连通分量
            if (!marked[v]) {
                dfs(c, v);
                // 连通分量标记+1
                count++;
            }

        }
    }

    /**
     * 深度优先搜索连通分量
     * @param v 起点
     */
    private void dfs(Stack<Iterator<Integer>> c, int v) {
        if (!marked[v]) {
            // 起点未标记，标记计数加1
            // 起点默认没标记，可以不加是否标记判断
            marked[v] = true;
            id[v] = count;
            size[count]++;
            Iterable<Integer> iterable = graph.adj(v);
            Iterator<Integer> it;
            if (iterable != null && (it = iterable.iterator()) != null){
                // 顶点对应的邻接表迭代器存入栈
                c.push(it);
            }
        }
        while (!c.isEmpty()) {
            Iterator<Integer> it = c.pop();
            int x;
            while (it.hasNext()) {
                // 邻接表迭代器有元素，获取元素
                x = it.next();
                if (!marked[x]) {
                    // 顶点未被标记，标记计数+1
                    marked[x] = true;
                    id[x] = count;
                    size[count]++;
                    if (it.hasNext()) {
                        // 邻接表迭代器有元素重新入栈
                        c.push(it);
                    }
                    // 深度优先原则，当前迭代器入栈，新标记顶点的邻接表迭代器入栈，下次循环优先访问
                    Iterable<Integer> iterable = graph.adj(x);
                    if (iterable != null && (it = iterable.iterator()) != null){
                        c.push(it);
                    }
                    break;
                }
            }

        }

    }

    /**
     * 广度优先搜索连通分量
     */
    private void bfs() {
        // 广度优先非递归实现，借助队列
        Queue<Integer> q = new Queue<>();
        // 搜索连通分量
        for (int v = 0; v < graph.V(); v++) {
            // 遍历图中所有顶点，以没有被标记过的顶点为起点，搜索连通分量
            // 执行完一次bsf，标记一个包含顶点v的连通分量
            if (!marked[v]) {
                bfs(q, v);
                // 连通分量标记+1
                count++;
            }

        }
    }

    private void bfs(Queue<Integer> q, int v) {
        marked[v] = true;
        id[v] = count;
        size[count]++;
        q.enqueue(v);
        while (!q.isEmpty()) {
            Integer x = q.dequeue();
            for (Integer w : graph.adj(x)) {
                if (!marked[w]) {
                    marked[w] = true;
                    id[w] = count;
                    size[count]++;
                    q.enqueue(w);
                }
            }
        }
    }


    /**
     * 给定顶点所在的连通分量标记
     * @param v 给定顶点
     * @return 顶点所在的连通分量标记
     * @throws IllegalArgumentException unless {@code 0<= v < V}
     */
    public int id(int v) {
        validateVertex(v);
        return id[v];
    }

    /**
     * 顶点v和w是否连通（是否在同一个连通分量内）
     * @param v 顶点v
     * @param w 顶点w
     * @return  {@code true} 如果{@code v}和{@code w}在同一个连通分量内；否则{@code false}
     * @throws IllegalArgumentException unless {@code 0 <= v < V}
     * @throws IllegalArgumentException unless {@code 0 <= w < V}
     */
    public boolean connected(int v, int w) {
        validateVertex(v);
        validateVertex(w);
        // 如果v和w在同一连通分量，那么连通分量标记相等；否则false
        return id[v] == id[w];
    }

    /**
     * 返回无向图{@code graph}中连通分量数量
     * @return  返回无向图{@code graph}中连通分量数量
     */
    public int count() {
        return count;
    }
    /**
     * 检查指定的顶点是否是有效顶点
     * @param v 给定顶点
     * @throws IllegalArgumentException unless {@code 0<= v < V}
     */
    private void validateVertex(int v) {
        int V = marked.length;
        if (v < 0 || v >= V) {
            throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1));
        }
    }

    public void display() {
        Map<Integer, ArrayList<Integer>> map = new HashMap<>(count);
        for (int i = 0; i < count; i++) {
            map.put(i, new ArrayList<>());
        }
        for (int i = 0; i < id.length; i++) {
            int k = id[i];
            ArrayList<Integer> list = map.get(k);
            list.add(i);
            map.put(k, list);
        }
        System.out.println("分量标记\t顶点数量\t顶点");
        for (int i = 0; i < count; i++) {
            ArrayList<Integer> l = map.get(i);
            System.out.println(i +"\t\t" + l.size() + "\t\t" + l);
        }
    }
}
